package seven_day;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一
 * 个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。时间复杂度小于O(n) ,空间复杂度O(1).
 */
public class FindValue {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String arr1 = scanner.nextLine().replaceAll("\\[", "").replaceAll("]", "");
        String arr2 = scanner.nextLine().replaceAll("\\[", "").replaceAll("]", "");
        System.out.println(arr1);
        System.out.println(arr2);
        String[] arr_part1 = arr1.split(", ");
        String[] arr_part2 = arr2.split(", ");
        int[][] arr = new int[][]{parseIntArr(arr_part1), parseIntArr(arr_part2)};
        int val = scanner.nextInt();
        System.out.println(findVal(arr, val));
    }


    public static int[] parseIntArr(String[] arr) {
        if (arr == null || arr.length == 0 || "".equals(arr[0])) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = Integer.parseInt(arr[i]);
        }
        return res;
    }

    public static boolean findVal(int[][] arr, int val) {
        // 判断arr为空
        if (arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0) {
            return false;
        }
        int row = arr.length; // 共有row行
        int col = arr[0].length; // 共有col列
        // 疑问：感觉遍历二维数组的时间复杂度是O(n^2) ？？？ 现在看来最坏的结果是O(n)!
        // 从第一行最后一个元素开始遍历，这个元素是第一行的最大值，最后一列的最小值，该元素所在的列可以直接判断该行或列是否符合条件
        int i = 0, j = col - 1;
        while (i < row && j >= 0) {
            if (arr[i][j] == val) {
                return true;
            }
            if (arr[i][j] < val) {
                // 当当前元素值小于了所找值则排除该行
                i ++;
                j = col - 1;
            } else {
                // 当前元素大于所找值
                j --;
            }
        }
        return false;
    }
}

